# Author    :Dun_Hz
# Time      :2024/7/29 8:46
# 插入排序

def insert_sort(li, gap):
    for i in range(gap, len(li)):
        j = i-gap       # 手里的牌
        tmp=li[i]
        while j>=0 and li[j]>tmp:
            li[j+gap] = li[j]
            j-=gap
        li[j+gap]=tmp

def shell_sort(li):
    d = len(li)//2
    while d>=1:
        insert_sort(li,d)
        d= d//2

if __name__=="__main__":
    li=[3,4,2,1,5,6,8,7,9]
    print(li)
    shell_sort(li)
    print(li)
